package com.example;



/**
 * @Author loubobooo
 * @Description # 69. x 的平方根
 * @Date 2019/12/26
 */
public class Sqrtx {
    /**
     * @return
     * @Author loubobooo
     * @Description 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
     * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
     * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
     * @Date 2019/12/26 16:16
     * @Param
     **/
    public int mySqrt(int x) {
        int left = 0, right = x;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if ((double) mid * mid < x){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return (double) left * left <= x ? left : left - 1;
    }

    public double mySqrt2(int c) {
        double xn;
        double x0 = c / 2;
        while(true){
            /**
             *  牛顿迭代法
             *  假设求根号6，x_0=6/2=3;
             *  x_1=(x_0+6/x_0)/2=2.5
             *  x_2=(x_1+6/x_1)/2=2.45，比较x_n - x_n-1的误差 < 1e-6
             */
            xn = (x0 + c/x0)/ 2;// ==>0.5*x1+0.5*c/x1;
            if(Math.abs(xn-x0) < 1e-6){
                break;
            }
            x0=xn;
        }
        // String.format("%.2f",x1); 保留到小数点后两位
        return x0;
    }


    public static void main(String[] args) {
        Sqrtx sqrtx = new Sqrtx();
        int[] a = new int[]{1,2,3};
        sqrtx.mySqrt2(5);
    }

}
